C++语言题解

P党再见

看见标签：DP，想DP我不会这样发不了题解，于是有以下思路

思路：最大差值……差值！（划重点）差值怎么办呢？当然是用差分了！

懂了的退出自己想想。

差分，具体怎么办呢？最大差值，即找出差分数组的最大子段和。特别地，这里差分数组第一个位置要置成非正数（因为不能取第一个数前面隐藏的0），否则样例会过不了。

样例解释

最大子段和为d[1]+d[2]+d[3]+d[4]+d[5]+d[6]，换回原数组即为a[1]-a[0]+a[2]-a[1]+a[3]-a[2]+a[4]-a[3]+a[5]-a[4]+a[6]-a[5]，即a[6]-a[0]，为最大差值。

代码：

#include <iostream>
#include <limits.h>
using namespace std;

int n, a[1000001], d[1000001], f[1000001];

int maxsum(void)
{
    f[0] = d[0];
    for(int i=1;i<n;i++) f[i] = max(f[i-1] + d[i], d[i]);
    int m = INT_MIN;
    for(int i=0;i<n;i++) m = max(m, f[i]);
    return m;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
	{
		cin>>a[i];
		d[i] = i ? (a[i] - a[i-1]) : -1000000;//差分 
	}
//	for(int i=0;i<n;i++) cout<<d[i]<<" ";
//	cout<<endl;
    cout<<maxsum()<<endl;
    return 0;
}